#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 4000;
struct Huffmannode {
    char data = ' ';
    int weight;
    bool isSingle;  // 是否为单节点
    int firstPos;   // 首次出现位置
    int createOrder; // 创建顺序
    Huffmannode *left, *right;
};
struct CharInfo {
    char data = ' ';
    int freq = 0;
    int first = -1;
};
CharInfo ch[maxn];
string huffmanCodes[maxn];
Huffmannode *trees[maxn];
int createCounter = 0; // 用于记录节点的创建顺序
struct compare{
    bool operator()(Huffmannode *a, Huffmannode *b) {
    if(a->weight != b->weight) 
        return a->weight > b->weight;
    // 权值相等时的处理
    if(a->isSingle && b->isSingle)
        return a->firstPos >b->firstPos;  // 单节点比较首次出现位置
    if(a->isSingle || b->isSingle)
        return !a->isSingle;  // 单节点优先
    return a->createOrder  >b->createOrder;  // 非单节点按创建顺序
}
};
bool compareOutput(CharInfo a, CharInfo b) {
    if(a.freq != b.freq) 
        return a.freq < b.freq;
    return a.first < b.first;
}
priority_queue<Huffmannode *,vector<Huffmannode *>,compare> q;
// 修改的构建哈夫曼树函数
Huffmannode* buildHuffmanTree(Huffmannode *forest[], int n) {
    int currSize = n;
    while(currSize > 1) {
        Huffmannode *newNode = new Huffmannode;
        newNode->left = q.top();
        q.pop();
        newNode->right = q.top();
        q.pop();
        newNode->weight = newNode->left->weight + newNode->right->weight;
        newNode->isSingle = false;
        newNode->createOrder = ++createCounter;
        q.push(newNode);
        // 移除已使用的两个节点
        currSize--;
    }
    return q.top();
}
void createHuffmanForest(CharInfo charInfo[], int n) {
    for(int i = 0; i < n; i++) {
        trees[i] = new Huffmannode;
        trees[i]->data = charInfo[i].data;
        trees[i]->weight = charInfo[i].freq;
        trees[i]->isSingle = true;
        trees[i]->firstPos = charInfo[i].first;
        trees[i]->createOrder = i;
        trees[i]->left = trees[i]->right = NULL;
        q.push(trees[i]);
    }
}
void generateHuffmanCodes(Huffmannode *root, string currentCode) {
    if (!root) return;
    if (!root->left && !root->right) {
        huffmanCodes[root->data] = currentCode;
        return;
    }
    generateHuffmanCodes(root->left, currentCode + "0");
    generateHuffmanCodes(root->right, currentCode + "1");
}
int calculateEncodedSize(CharInfo charInfo[], int n) {
    int totalBits = 0;
    for(int i = 0; i < n; i++) {
        totalBits += charInfo[i].freq * huffmanCodes[charInfo[i].data].length();
    }
    return (totalBits + 7) / 8;//向上取整
}
bool decode(Huffmannode *root, const string &encoded, string &decoded) {
    Huffmannode *current = root;
    decoded = "";
    for(char bit : encoded) {
        if(bit == '0') {
            if(!current->left) return false;
            current = current->left;
        } else if(bit == '1') {
            if(!current->right) return false;
            current = current->right;
        }
        if(!current->left && !current->right) {
            decoded += current->data;
            current = root;
        }
    }
    return current == root;
}
int main() {
    string text;
    cin >> text;
    // 统计字符频率和首次出现位置
    int charFreq[256] = {0};
    int firstOccurrence[256];
    memset(firstOccurrence, -1, sizeof(firstOccurrence));
    for(int i = 0; i < text.length(); i++) {
        charFreq[text[i]]++;
        if(firstOccurrence[text[i]] == -1) {
            firstOccurrence[text[i]] = i;
        }
    }
    // 收集字符信息
    int uniqueChars = 0;
    for(int i = 0; i < 256; i++) {
        if(charFreq[i]) {
            ch[uniqueChars].data = char(i);
            ch[uniqueChars].freq = charFreq[i];
            ch[uniqueChars].first = firstOccurrence[i];
            uniqueChars++;
        }
    }
    // 创建并构建哈夫曼树
    createCounter = 0;
    createHuffmanForest(ch, uniqueChars);
    Huffmannode *root = buildHuffmanTree(trees, uniqueChars);
    generateHuffmanCodes(root, "");
    // 输出压缩信息
    cout << text.length() << " " << calculateEncodedSize(ch, uniqueChars) << endl;
    // 按要求排序并输出编码
    sort(ch, ch + uniqueChars, compareOutput);
    for(int i = 0; i < uniqueChars; i++) {
        cout << ch[i].data << ":" << huffmanCodes[ch[i].data] << endl;
    }
    // 解码
    string encoded1, encoded2;
    cin >> encoded1 >> encoded2;
    string decoded1, decoded2;
    if(decode(root, encoded1, decoded1)) {
        cout << decoded1 << endl;
    } else {
        cout << "INVALID" << endl;
    }
    if(decode(root, encoded2, decoded2)) {
        cout << decoded2 << endl;
    } else {
        cout << "INVALID" << endl;
    }
    return 0;
}//记录每个字母频率。
//对每一个进行建节点，入队。
//每次取两个最小的节点，左边小，右边大合并后，入队。
//直到只剩一个，队中唯一一个就是根节点。
//解码：0左1右，访问到叶节点将结果加入字符串，回到根。